public class Test36 {
    public static int inversePairs(int[] data){
        if (data == null ||data.length == 0) throw new IllegalArgumentException("invalid");
        int[] copy = new int[data.length];
        System.arraycopy(data,0,copy,0,data.length);
        return inversePairsCore(data,copy,0,data.length-1);
    }
    public static int inversePairsCore(int[] data,int[] copy,int start,int end){
        if (start == end){
            data[start] = copy[end];
            return 0;
        }
        int length = (end -start)/2;
        int left = inversePairsCore(data,copy,start,start+length); //递归
        int right = inversePairsCore(data,copy,start+length+1,end);

        int i = start+length;//第一个数组的末尾
        int j = end;//第二个数组的末尾
        //拷贝的位置，从后往前拷贝
        int indexcopy = end;
        //逆序对
        int count = 0;

        while (i>= start &&j >= start+length+1){
            if (data[i]>data[j]){
                copy[indexcopy] = data[i];
                indexcopy --;
                i --;
                count += j-(start+length);
            }else {
                copy[indexcopy] = data[j];
                indexcopy --;
                j--;
            }
        }
        //把剩余的元素加入到copy中
        for (;i>= start;i--){
            copy[indexcopy] = data[i];
            indexcopy --;
        }
        for (;j>= start+length+1;j--){
            copy[indexcopy] = data[j];
            indexcopy --;
        }
        return count+left+right;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 7, 6, 5};
        System.out.println(inversePairs(data)); // 3
    }

}
